/ Giga Games 1 / Giga Games.iso / net / go / comp / mcgo.tex / node9_ct.html

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 3c 21 44 4f 43 54 59 50 | 45 20 48 54 4d 4c 20 50 |<!DOCTYP|E HTML P|
|00000010| 55 42 4c 49 43 20 22 2d | 2f 2f 57 33 43 2f 2f 44 |UBLIC "-|//W3C//D|
|00000020| 54 44 20 48 54 4d 4c 20 | 33 2e 32 20 46 69 6e 61 |TD HTML |3.2 Fina|
|00000030| 6c 2f 2f 65 6e 22 3e 0a | 0a 3c 21 2d 2d 43 6f 6e |l//en">.|.<!--Con|
|00000040| 76 65 72 74 65 64 20 77 | 69 74 68 20 4c 61 54 65 |verted w|ith LaTe|
|00000050| 58 32 48 54 4d 4c 20 32 | 30 32 32 20 28 52 65 6c |X2HTML 2|022 (Rel|
|00000060| 65 61 73 65 64 20 4a 61 | 6e 75 61 72 79 20 31 2c |eased Ja|nuary 1,|
|00000070| 20 32 30 32 32 29 20 2d | 2d 3e 0a 3c 48 54 4d 4c | 2022) -|->.<HTML|
|00000080| 20 6c 61 6e 67 3d 22 65 | 6e 22 3e 0a 3c 48 45 41 | lang="e|n">.<HEA|
|00000090| 44 3e 0a 3c 54 49 54 4c | 45 3e 43 6f 6e 74 65 6e |D>.<TITL|E>Conten|
|000000a0| 74 73 20 6f 66 20 47 6f | 62 62 6c 65 3a 20 61 20 |ts of Go|bble: a |
|000000b0| 70 72 6f 67 72 61 6d 20 | 70 6c 61 79 73 20 4d 6f |program |plays Mo|
|000000c0| 6e 74 65 20 43 61 72 6c | 6f 20 67 6f 3c 2f 54 49 |nte Carl|o go</TI|
|000000d0| 54 4c 45 3e 0a 0a 3c 4d | 45 54 41 20 48 54 54 50 |TLE>..<M|ETA HTTP|
|000000e0| 2d 45 51 55 49 56 3d 22 | 43 6f 6e 74 65 6e 74 2d |-EQUIV="|Content-|
|000000f0| 54 79 70 65 22 20 43 4f | 4e 54 45 4e 54 3d 22 74 |Type" CO|NTENT="t|
|00000100| 65 78 74 2f 68 74 6d 6c | 3b 20 63 68 61 72 73 65 |ext/html|; charse|
|00000110| 74 3d 75 74 66 2d 38 22 | 3e 0a 3c 4d 45 54 41 20 |t=utf-8"|>.<META |
|00000120| 4e 41 4d 45 3d 22 76 69 | 65 77 70 6f 72 74 22 20 |NAME="vi|ewport" |
|00000130| 43 4f 4e 54 45 4e 54 3d | 22 77 69 64 74 68 3d 64 |CONTENT=|"width=d|
|00000140| 65 76 69 63 65 2d 77 69 | 64 74 68 2c 20 69 6e 69 |evice-wi|dth, ini|
|00000150| 74 69 61 6c 2d 73 63 61 | 6c 65 3d 31 2e 30 22 3e |tial-sca|le=1.0">|
|00000160| 0a 3c 4d 45 54 41 20 4e | 41 4d 45 3d 22 47 65 6e |.<META N|AME="Gen|
|00000170| 65 72 61 74 6f 72 22 20 | 43 4f 4e 54 45 4e 54 3d |erator" |CONTENT=|
|00000180| 22 4c 61 54 65 58 32 48 | 54 4d 4c 20 76 32 30 32 |"LaTeX2H|TML v202|
|00000190| 32 22 3e 0a 0a 3c 4c 49 | 4e 4b 20 52 45 4c 3d 22 |2">..<LI|NK REL="|
|000001a0| 53 54 59 4c 45 53 48 45 | 45 54 22 20 48 52 45 46 |STYLESHE|ET" HREF|
|000001b0| 3d 22 6d 63 67 6f 2e 63 | 73 73 22 3e 0a 0a 3c 4c |="mcgo.c|ss">..<L|
|000001c0| 49 4e 4b 20 52 45 4c 3d | 22 6e 65 78 74 22 20 48 |INK REL=|"next" H|
|000001d0| 52 45 46 3d 22 6e 6f 64 | 65 31 30 5f 6d 6e 2e 68 |REF="nod|e10_mn.h|
|000001e0| 74 6d 6c 22 3e 0a 3c 4c | 49 4e 4b 20 52 45 4c 3d |tml">.<L|INK REL=|
|000001f0| 22 70 72 65 76 69 6f 75 | 73 22 20 48 52 45 46 3d |"previou|s" HREF=|
|00000200| 22 6e 6f 64 65 38 5f 6d | 6e 2e 68 74 6d 6c 22 3e |"node8_m|n.html">|
|00000210| 0a 3c 4c 49 4e 4b 20 52 | 45 4c 3d 22 75 70 22 20 |.<LINK R|EL="up" |
|00000220| 48 52 45 46 3d 22 6d 63 | 67 6f 5f 6d 6e 2e 68 74 |HREF="mc|go_mn.ht|
|00000230| 6d 6c 22 3e 0a 3c 4c 49 | 4e 4b 20 52 45 4c 3d 22 |ml">.<LI|NK REL="|
|00000240| 6e 65 78 74 22 20 48 52 | 45 46 3d 22 6e 6f 64 65 |next" HR|EF="node|
|00000250| 31 30 5f 6d 6e 2e 68 74 | 6d 6c 22 3e 0a 3c 2f 48 |10_mn.ht|ml">.</H|
|00000260| 45 41 44 3e 0a 20 0a 3c | 42 4f 44 59 20 62 67 63 |EAD>. .<|BODY bgc|
|00000270| 6f 6c 6f 72 3d 22 23 66 | 66 66 66 66 66 22 20 74 |olor="#f|fffff" t|
|00000280| 65 78 74 3d 22 23 30 30 | 30 30 30 30 22 20 6c 69 |ext="#00|0000" li|
|00000290| 6e 6b 3d 22 23 39 39 34 | 34 45 45 22 20 76 6c 69 |nk="#994|4EE" vli|
|000002a0| 6e 6b 3d 22 23 30 30 30 | 30 66 66 22 20 61 6c 69 |nk="#000|0ff" ali|
|000002b0| 6e 6b 3d 22 23 30 30 66 | 66 30 30 22 3e 0a 0a 3c |nk="#00f|f00">..<|
|000002c0| 48 32 3e 3c 41 20 49 44 | 3d 22 53 45 43 54 49 4f |H2><A ID|="SECTIO|
|000002d0| 4e 30 30 30 30 39 30 30 | 30 30 30 30 30 30 30 30 |N0000900|00000000|
|000002e0| 30 30 30 30 30 22 3e 0a | 47 6f 62 62 6c 65 3a 20 |00000">.|Gobble: |
|000002f0| 61 20 70 72 6f 67 72 61 | 6d 20 70 6c 61 79 73 20 |a progra|m plays |
|00000300| 4d 6f 6e 74 65 20 43 61 | 72 6c 6f 20 67 6f 3c 2f |Monte Ca|rlo go</|
|00000310| 41 3e 0a 3c 2f 48 32 3e | 0a 0a 3c 50 3e 0a 49 6e |A>.</H2>|..<P>.In|
|00000320| 20 74 68 69 73 20 73 65 | 63 74 69 6f 6e 20 77 65 | this se|ction we|
|00000330| 20 70 72 65 73 65 6e 74 | 20 72 65 73 75 6c 74 73 | present| results|
|00000340| 20 6f 62 74 61 69 6e 65 | 64 20 77 69 74 68 20 74 | obtaine|d with t|
|00000350| 68 65 20 63 6f 6d 70 75 | 74 65 72 20 70 72 6f 67 |he compu|ter prog|
|00000360| 72 61 6d 0a 47 6f 62 62 | 6c 65 20 28 76 65 72 73 |ram.Gobb|le (vers|
|00000370| 69 6f 6e 20 31 2e 30 29 | 20 74 68 61 74 20 70 6c |ion 1.0)| that pl|
|00000380| 61 79 73 20 67 6f 20 6f | 6e 20 74 68 65 20 39 78 |ays go o|n the 9x|
|00000390| 39 20 62 6f 61 72 64 20 | 75 73 69 6e 67 20 73 69 |9 board |using si|
|000003a0| 6d 75 6c 61 74 65 64 0a | 61 6e 6e 65 61 6c 69 6e |mulated.|annealin|
|000003b0| 67 20 74 6f 20 66 69 6e | 64 20 60 60 74 68 65 20 |g to fin|d ``the |
|000003c0| 62 65 73 74 27 27 20 6d | 6f 76 65 2e 20 54 68 65 |best'' m|ove. The|
|000003d0| 20 70 6f 69 6e 74 20 69 | 73 20 74 68 61 74 20 6e | point i|s that n|
|000003e0| 6f 74 68 69 6e 67 20 6d | 6f 72 65 0a 74 68 61 6e |othing m|ore.than|
|000003f0| 20 73 69 6d 75 6c 61 74 | 65 64 20 61 6e 6e 65 61 | simulat|ed annea|
|00000400| 6c 69 6e 67 20 69 73 20 | 69 6d 70 6c 65 6d 65 6e |ling is |implemen|
|00000410| 74 65 64 20 6f 6e 20 74 | 6f 70 20 6f 66 20 74 68 |ted on t|op of th|
|00000420| 65 20 62 61 72 65 20 67 | 6f 20 70 6c 61 79 69 6e |e bare g|o playin|
|00000430| 67 0a 72 75 6c 65 73 20 | 74 6f 20 61 6c 6c 6f 77 |g.rules |to allow|
|00000440| 20 75 73 20 74 6f 20 73 | 74 75 64 79 20 74 68 65 | us to s|tudy the|
|00000450| 20 6d 65 74 68 6f 64 2e | 0a 0a 3c 50 3e 0a 57 65 | method.|..<P>.We|
|00000460| 20 77 69 6c 6c 20 6e 6f | 74 20 64 65 73 63 72 69 | will no|t descri|
|00000470| 62 65 20 74 68 65 20 70 | 72 6f 67 72 61 6d 20 69 |be the p|rogram i|
|00000480| 6e 20 64 65 74 61 69 6c | 2c 20 73 69 6e 63 65 20 |n detail|, since |
|00000490| 74 68 69 73 20 77 6f 75 | 6c 64 20 6f 62 73 63 75 |this wou|ld obscu|
|000004a0| 72 65 0a 72 61 74 68 65 | 72 20 74 68 61 6e 20 68 |re.rathe|r than h|
|000004b0| 65 6c 70 20 74 68 65 20 | 67 65 6e 65 72 61 6c 20 |elp the |general |
|000004c0| 64 69 73 63 75 73 73 69 | 6f 6e 2e 20 41 6e 79 6f |discussi|on. Anyo|
|000004d0| 6e 65 20 77 69 74 68 20 | 73 6f 6d 65 20 65 78 70 |ne with |some exp|
|000004e0| 65 72 69 65 6e 63 65 0a | 69 6e 20 70 72 6f 67 72 |erience.|in progr|
|000004f0| 61 6d 6d 69 6e 67 20 77 | 69 6c 6c 20 61 67 72 65 |amming w|ill agre|
|00000500| 65 20 74 68 61 74 20 61 | 6e 20 69 6d 70 6c 65 6d |e that a|n implem|
|00000510| 65 6e 74 61 74 69 6f 6e | 20 6f 66 20 74 68 65 20 |entation| of the |
|00000520| 61 6c 67 6f 72 69 74 68 | 6d 0a 73 68 6f 75 6c 64 |algorith|m.should|
|00000530| 20 62 65 20 73 74 72 61 | 69 67 68 74 66 6f 72 77 | be stra|ightforw|
|00000540| 61 72 64 2e 20 20 4f 6e | 65 20 74 65 63 68 6e 69 |ard.  On|e techni|
|00000550| 63 61 6c 20 69 73 73 75 | 65 20 77 65 20 68 61 76 |cal issu|e we hav|
|00000560| 65 20 74 6f 20 6d 65 6e | 74 69 6f 6e 20 69 73 0a |e to men|tion is.|
|00000570| 68 6f 77 20 77 65 20 64 | 65 66 69 6e 65 20 74 68 |how we d|efine th|
|00000580| 65 20 65 6e 64 20 6f 66 | 20 61 20 67 61 6d 65 20 |e end of| a game |
|00000590| 28 72 65 63 61 6c 6c 20 | 74 68 61 74 20 77 65 20 |(recall |that we |
|000005a0| 77 61 6e 74 20 74 6f 20 | 70 6c 61 79 20 67 61 6d |want to |play gam|
|000005b0| 65 73 0a 72 6f 75 74 69 | 6e 65 6c 79 20 74 6f 20 |es.routi|nely to |
|000005c0| 74 68 65 20 76 65 72 79 | 20 65 6e 64 29 2e 20 4f |the very| end). O|
|000005d0| 6e 20 66 69 72 73 74 20 | 73 69 67 68 74 20 74 68 |n first |sight th|
|000005e0| 69 73 20 69 73 20 61 74 | 20 6c 65 61 73 74 0a 69 |is is at| least.i|
|000005f0| 6e 74 75 69 74 69 76 65 | 6c 79 20 63 6c 65 61 72 |ntuitive|ly clear|
|00000600| 20 74 6f 20 68 75 6d 61 | 6e 20 70 6c 61 79 65 72 | to huma|n player|
|00000610| 73 2c 20 62 75 74 20 77 | 68 69 6c 65 20 74 68 65 |s, but w|hile the|
|00000620| 20 72 75 6c 65 73 20 66 | 6f 72 20 70 6c 61 79 69 | rules f|or playi|
|00000630| 6e 67 0a 6d 6f 76 65 73 | 20 69 6e 20 67 6f 20 61 |ng.moves| in go a|
|00000640| 72 65 20 65 6c 65 67 61 | 6e 74 20 61 6e 64 20 73 |re elega|nt and s|
|00000650| 69 6d 70 6c 65 2c 20 72 | 75 6c 65 73 20 66 6f 72 |imple, r|ules for|
|00000660| 20 77 68 65 6e 20 74 68 | 65 20 67 61 6d 65 20 65 | when th|e game e|
|00000670| 6e 64 73 20 61 6e 64 0a | 68 6f 77 20 74 68 65 20 |nds and.|how the |
|00000680| 72 65 73 75 6c 74 20 69 | 73 20 74 6f 20 62 65 20 |result i|s to be |
|00000690| 63 6f 75 6e 74 65 64 20 | 61 72 65 20 73 75 72 70 |counted |are surp|
|000006a0| 72 69 73 69 6e 67 6c 79 | 20 63 6f 6d 70 6c 65 78 |risingly| complex|
|000006b0| 2e 20 54 68 65 20 6c 61 | 74 74 65 72 0a 74 77 6f |. The la|tter.two|
|000006c0| 20 69 73 73 75 65 73 20 | 61 72 65 20 72 65 6c 61 | issues |are rela|
|000006d0| 74 65 64 2c 20 61 6e 64 | 20 74 68 65 72 65 20 61 |ted, and| there a|
|000006e0| 72 65 20 69 6e 20 66 61 | 63 74 20 64 69 66 66 65 |re in fa|ct diffe|
|000006f0| 72 65 6e 74 20 28 4a 61 | 70 61 6e 65 73 65 2c 0a |rent (Ja|panese,.|
|00000700| 43 68 69 6e 65 73 65 2c | 20 2e 2e 2e 29 20 72 75 |Chinese,| ...) ru|
|00000710| 6c 65 73 20 77 68 69 63 | 68 20 69 6e 20 72 61 72 |les whic|h in rar|
|00000720| 65 20 63 61 73 65 73 20 | 6c 69 6b 65 20 61 20 6d |e cases |like a m|
|00000730| 75 6c 74 69 6c 70 6c 65 | 20 6b 6f 20 6f 72 20 73 |ultilple| ko or s|
|00000740| 70 65 63 69 61 6c 0a 73 | 65 6b 69 20 67 69 76 65 |pecial.s|eki give|
|00000750| 20 73 6c 69 67 68 74 6c | 79 20 64 69 66 66 65 72 | slightl|y differ|
|00000760| 65 6e 74 20 72 65 73 75 | 6c 74 73 2e 0a 0a 3c 50 |ent resu|lts...<P|
|00000770| 3e 0a 57 65 20 61 64 6f | 70 74 20 66 6f 72 20 74 |>.We ado|pt for t|
|00000780| 68 65 20 6d 6f 6d 65 6e | 74 20 74 68 65 20 66 6f |he momen|t the fo|
|00000790| 6c 6c 6f 77 69 6e 67 20 | 70 72 65 73 63 72 69 70 |llowing |prescrip|
|000007a0| 74 69 6f 6e 2e 20 54 68 | 65 20 63 6f 6d 70 75 74 |tion. Th|e comput|
|000007b0| 65 72 20 6f 6e 6c 79 0a | 70 61 73 73 65 73 20 69 |er only.|passes i|
|000007c0| 66 20 65 69 74 68 65 72 | 20 6e 6f 20 6c 65 67 61 |f either| no lega|
|000007d0| 6c 20 6d 6f 76 65 20 69 | 73 20 61 76 61 69 6c 61 |l move i|s availa|
|000007e0| 62 6c 65 20 6f 72 20 61 | 6c 6c 20 6c 65 67 61 6c |ble or a|ll legal|
|000007f0| 20 6d 6f 76 65 73 20 72 | 65 64 75 63 65 0a 74 68 | moves r|educe.th|
|00000800| 65 20 65 79 65 20 73 70 | 61 63 65 20 6f 66 20 6f |e eye sp|ace of o|
|00000810| 6e 65 20 6f 66 20 69 74 | 73 20 67 72 6f 75 70 73 |ne of it|s groups|
|00000820| 20 66 72 6f 6d 20 74 77 | 6f 20 74 6f 20 6f 6e 65 | from tw|o to one|
|00000830| 2e 20 20 54 68 65 20 28 | 6f 76 65 72 2d 29 0a 73 |.  The (|over-).s|
|00000840| 69 6d 70 6c 69 66 69 63 | 61 74 69 6f 6e 20 6c 69 |implific|ation li|
|00000850| 65 73 20 69 6e 20 74 68 | 65 20 64 65 66 69 6e 69 |es in th|e defini|
|00000860| 74 69 6f 6e 20 6f 66 20 | 61 6e 20 65 79 65 2c 20 |tion of |an eye, |
|00000870| 77 68 69 63 68 20 69 73 | 20 64 65 66 69 6e 65 64 |which is| defined|
|00000880| 20 74 6f 0a 62 65 20 61 | 20 66 69 65 6c 64 20 77 | to.be a| field w|
|00000890| 68 6f 73 65 20 64 69 72 | 65 63 74 20 6e 65 69 67 |hose dir|ect neig|
|000008a0| 68 62 6f 72 73 20 61 72 | 65 20 61 6c 6c 20 6f 66 |hbors ar|e all of|
|000008b0| 20 74 68 65 20 73 61 6d | 65 20 63 6f 6c 6f 72 20 | the sam|e color |
|000008c0| 61 6e 64 20 77 68 6f 73 | 65 0a 64 69 61 67 6f 6e |and whos|e.diagon|
|000008d0| 61 6c 20 6e 65 69 67 68 | 62 6f 72 73 20 63 6f 6e |al neigh|bors con|
|000008e0| 74 61 69 6e 20 6e 6f 20 | 6d 6f 72 65 20 74 68 61 |tain no |more tha|
|000008f0| 6e 20 31 20 73 74 6f 6e | 65 20 6f 66 20 74 68 65 |n 1 ston|e of the|
|00000900| 20 6f 70 70 6f 73 69 74 | 65 20 63 6f 6c 6f 72 0a | opposit|e color.|
|00000910| 28 30 20 66 6f 72 20 62 | 6f 72 64 65 72 20 61 6e |(0 for b|order an|
|00000920| 64 20 63 6f 72 6e 65 72 | 20 66 69 65 6c 64 73 29 |d corner| fields)|
|00000930| 2e 20 54 68 65 20 72 65 | 61 64 65 72 20 6d 61 79 |. The re|ader may|
|00000940| 20 63 6f 6e 76 69 6e 63 | 65 20 68 69 6d 73 65 6c | convinc|e himsel|
|00000950| 66 20 74 68 61 74 0a 74 | 68 69 73 20 64 65 66 69 |f that.t|his defi|
|00000960| 6e 69 74 69 6f 6e 20 6f | 66 20 61 6e 20 65 79 65 |nition o|f an eye|
|00000970| 20 69 73 20 63 6f 72 72 | 65 63 74 20 66 6f 72 20 | is corr|ect for |
|00000980| 6d 6f 73 74 20 73 69 74 | 75 61 74 69 6f 6e 73 2c |most sit|uations,|
|00000990| 20 65 78 63 6c 75 64 69 | 6e 67 0a 73 65 6b 69 73 | excludi|ng.sekis|
|000009a0| 2e 20 57 68 65 6e 20 62 | 6f 74 68 20 73 69 64 65 |. When b|oth side|
|000009b0| 73 20 68 61 76 65 20 74 | 6f 20 70 61 73 73 2c 20 |s have t|o pass, |
|000009c0| 74 68 65 20 67 61 6d 65 | 20 69 73 20 6f 76 65 72 |the game| is over|
|000009d0| 20 61 6e 64 20 74 68 65 | 20 72 65 73 75 6c 74 20 | and the| result |
|000009e0| 69 73 0a 64 65 74 65 72 | 6d 69 6e 65 64 20 76 69 |is.deter|mined vi|
|000009f0| 61 20 43 68 69 6e 65 73 | 65 20 63 6f 75 6e 74 69 |a Chines|e counti|
|00000a00| 6e 67 2e 20 54 68 65 73 | 65 20 61 72 65 20 73 74 |ng. Thes|e are st|
|00000a10| 61 6e 64 61 72 64 20 72 | 75 6c 65 73 20 65 78 63 |andard r|ules exc|
|00000a20| 65 70 74 20 74 68 61 74 | 0a 74 68 65 20 63 6f 6d |ept that|.the com|
|00000a30| 70 75 74 65 72 20 70 6c | 61 79 65 72 20 64 6f 65 |puter pl|ayer doe|
|00000a40| 73 20 6e 6f 74 20 72 65 | 61 6c 69 7a 65 20 74 68 |s not re|alize th|
|00000a50| 61 74 20 73 74 6f 6e 65 | 73 20 69 6e 20 61 20 73 |at stone|s in a s|
|00000a60| 65 6b 69 20 61 72 65 20 | 61 6c 69 76 65 2e 0a 53 |eki are |alive..S|
|00000a70| 65 6b 69 73 20 63 61 6e | 20 62 65 20 64 65 61 6c |ekis can| be deal|
|00000a80| 74 20 77 69 74 68 20 6f | 6e 63 65 20 70 61 73 73 |t with o|nce pass|
|00000a90| 69 6e 67 20 69 73 20 61 | 6c 6c 6f 77 65 64 20 61 |ing is a|llowed a|
|00000aa0| 73 20 61 6e 20 6f 70 74 | 69 6f 6e 2c 20 62 75 74 |s an opt|ion, but|
|00000ab0| 20 77 65 0a 6c 65 61 76 | 65 20 69 74 20 61 74 20 | we.leav|e it at |
|00000ac0| 74 68 61 74 20 66 6f 72 | 20 73 69 6d 70 6c 69 63 |that for| simplic|
|00000ad0| 69 74 79 20 61 6e 64 20 | 73 70 65 65 64 2e 0a 0a |ity and |speed...|
|00000ae0| 3c 50 3e 0a 4c 65 74 20 | 75 73 20 61 6c 73 6f 20 |<P>.Let |us also |
|00000af0| 6d 65 6e 74 69 6f 6e 20 | 61 20 66 65 77 20 70 6f |mention |a few po|
|00000b00| 69 6e 74 73 20 61 62 6f | 75 74 20 74 68 65 20 70 |ints abo|ut the p|
|00000b10| 72 6f 62 61 62 69 6c 69 | 73 74 69 63 20 61 73 70 |robabili|stic asp|
|00000b20| 65 63 74 73 20 6f 66 0a | 74 68 65 20 70 72 6f 67 |ects of.|the prog|
|00000b30| 72 61 6d 20 61 6e 64 20 | 74 68 65 20 61 6e 6e 65 |ram and |the anne|
|00000b40| 61 6c 69 6e 67 20 73 63 | 68 65 64 75 6c 65 2e 20 |aling sc|hedule. |
|00000b50| 44 65 74 65 72 6d 69 6e | 61 74 69 6f 6e 20 6f 66 |Determin|ation of|
|00000b60| 20 61 20 67 6f 6f 64 0a | 61 6e 6e 65 61 6c 69 6e | a good.|annealin|
|00000b70| 67 20 73 63 68 65 64 75 | 6c 65 20 69 73 20 61 20 |g schedu|le is a |
|00000b80| 6d 61 74 74 65 72 20 6f | 66 20 65 78 70 65 72 69 |matter o|f experi|
|00000b90| 6d 65 6e 74 61 74 69 6f | 6e 20 5b 3c 41 20 48 52 |mentatio|n [<A HR|
|00000ba0| 45 46 3d 22 6e 6f 64 65 | 31 34 5f 63 74 2e 68 74 |EF="node|14_ct.ht|
|00000bb0| 6d 6c 23 6e 75 6d 72 65 | 63 22 20 54 41 52 47 45 |ml#numre|c" TARGE|
|00000bc0| 54 3d 22 63 6f 6e 74 65 | 6e 74 73 22 3e 32 3c 2f |T="conte|nts">2</|
|00000bd0| 41 3e 5d 2c 20 68 65 72 | 65 0a 69 73 20 77 68 61 |A>], her|e.is wha|
|00000be0| 74 20 77 65 20 66 6f 75 | 6e 64 20 75 73 65 66 75 |t we fou|nd usefu|
|00000bf0| 6c 2e 20 46 69 72 73 74 | 20 77 65 20 6f 72 64 65 |l. First| we orde|
|00000c00| 72 20 74 68 65 20 6d 6f | 76 65 73 20 73 74 72 69 |r the mo|ves stri|
|00000c10| 63 74 6c 79 20 62 79 20 | 76 61 6c 75 65 2c 0a 77 |ctly by |value,.w|
|00000c20| 68 69 63 68 20 63 6f 72 | 72 65 73 70 6f 6e 64 73 |hich cor|responds|
|00000c30| 20 74 6f 20 61 20 70 72 | 6f 62 61 62 69 6c 69 74 | to a pr|obabilit|
|00000c40| 79 20 6f 66 20 31 20 74 | 68 61 74 20 61 20 6d 6f |y of 1 t|hat a mo|
|00000c50| 76 65 20 77 69 74 68 20 | 62 65 74 74 65 72 20 76 |ve with |better v|
|00000c60| 61 6c 75 65 0a 69 73 20 | 70 6c 61 79 65 64 20 66 |alue.is |played f|
|00000c70| 69 72 73 74 2e 20 54 68 | 65 6e 20 77 65 20 73 77 |irst. Th|en we sw|
|00000c80| 65 65 70 20 6f 76 65 72 | 20 74 68 65 20 6c 69 73 |eep over| the lis|
|00000c90| 74 20 6f 6e 63 65 20 66 | 72 6f 6d 20 62 65 73 74 |t once f|rom best|
|00000ca0| 20 74 6f 20 77 6f 72 73 | 74 0a 6d 6f 76 65 20 61 | to wors|t.move a|
|00000cb0| 6e 64 20 73 77 69 74 63 | 68 20 74 68 65 20 6f 72 |nd switc|h the or|
|00000cc0| 64 65 72 20 6f 66 20 74 | 77 6f 20 6e 65 69 67 68 |der of t|wo neigh|
|00000cd0| 62 6f 72 69 6e 67 20 6d | 6f 76 65 73 20 77 69 74 |boring m|oves wit|
|00000ce0| 68 20 70 72 6f 62 61 62 | 69 6c 69 74 79 20 0a 3c |h probab|ility .<|
|00000cf0| 49 3e 70 3c 2f 49 3e 3c | 53 55 42 3e 73 77 61 70 |I>p</I><|SUB>swap|
|00000d00| 3c 2f 53 55 42 3e 2e 20 | 54 68 65 20 70 72 6f 62 |</SUB>. |The prob|
|00000d10| 61 62 69 6c 69 74 79 20 | 3c 49 3e 70 3c 2f 49 3e |ability |<I>p</I>|
|00000d20| 28 3c 49 3e 6e 3c 2f 49 | 3e 29 20 74 68 61 74 20 |(<I>n</I|>) that |
|00000d30| 61 20 6d 6f 76 65 20 69 | 73 20 73 68 69 66 74 65 |a move i|s shifte|
|00000d40| 64 20 3c 49 3e 6e 3c 2f | 49 3e 26 23 38 38 30 35 |d <I>n</|I>&#8805|
|00000d50| 3b 31 20 0a 73 74 65 70 | 73 20 64 6f 77 6e 20 74 |;1 .step|s down t|
|00000d60| 68 65 20 6c 69 73 74 20 | 69 73 20 0a 3c 42 52 3e |he list |is .<BR>|
|00000d70| 0a 3c 44 49 56 20 41 4c | 49 47 4e 3d 22 43 45 4e |.<DIV AL|IGN="CEN|
|00000d80| 54 45 52 22 3e 0a 3c 21 | 2d 2d 20 4d 41 54 48 0a |TER">.<!|-- MATH.|
|00000d90| 20 5c 62 65 67 69 6e 7b | 65 71 6e 61 72 72 61 79 | \begin{|eqnarray|
|00000da0| 7d 0a 70 28 6e 29 20 26 | 3d 26 20 28 70 5f 7b 73 |}.p(n) &|=& (p_{s|
|00000db0| 77 61 70 7d 29 5e 6e 20 | 3d 20 5c 65 78 70 20 28 |wap})^n |= \exp (|
|00000dc0| 2d 6e 2f 54 29 2c 20 5c | 5c 0a 54 20 20 20 20 26 |-n/T), \|\.T    &|
|00000dd0| 3d 26 20 2d 31 2f 20 5c | 6c 6e 20 70 5f 7b 73 77 |=& -1/ \|ln p_{sw|
|00000de0| 61 70 7d 20 5c 67 65 71 | 20 30 2e 0a 5c 65 6e 64 |ap} \geq| 0..\end|
|00000df0| 7b 65 71 6e 61 72 72 61 | 79 7d 0a 20 2d 2d 3e 0a |{eqnarra|y}. -->.|
|00000e00| 3c 54 41 42 4c 45 20 43 | 45 4c 4c 50 41 44 44 49 |<TABLE C|ELLPADDI|
|00000e10| 4e 47 3d 22 30 22 20 41 | 4c 49 47 4e 3d 22 43 45 |NG="0" A|LIGN="CE|
|00000e20| 4e 54 45 52 22 20 57 49 | 44 54 48 3d 22 31 30 30 |NTER" WI|DTH="100|
|00000e30| 25 22 3e 0a 3c 54 52 20 | 56 41 4c 49 47 4e 3d 22 |%">.<TR |VALIGN="|
|00000e40| 4d 49 44 44 4c 45 22 3e | 3c 54 44 20 4e 4f 57 52 |MIDDLE">|<TD NOWR|
|00000e50| 41 50 20 41 4c 49 47 4e | 3d 22 52 49 47 48 54 22 |AP ALIGN|="RIGHT"|
|00000e60| 3e 3c 49 3e 70 3c 2f 49 | 3e 28 3c 49 3e 6e 3c 2f |><I>p</I|>(<I>n</|
|00000e70| 49 3e 29 3c 2f 54 44 3e | 0a 3c 54 44 20 57 49 44 |I>)</TD>|.<TD WID|
|00000e80| 54 48 3d 22 31 30 22 20 | 41 4c 49 47 4e 3d 22 43 |TH="10" |ALIGN="C|
|00000e90| 45 4e 54 45 52 22 20 4e | 4f 57 52 41 50 3e 3d 3c |ENTER" N|OWRAP>=<|
|00000ea0| 2f 54 44 3e 0a 3c 54 44 | 20 41 4c 49 47 4e 3d 22 |/TD>.<TD| ALIGN="|
|00000eb0| 4c 45 46 54 22 20 4e 4f | 57 52 41 50 3e 28 3c 49 |LEFT" NO|WRAP>(<I|
|00000ec0| 3e 70 3c 2f 49 3e 3c 53 | 55 42 3e 73 77 61 70 3c |>p</I><S|UB>swap<|
|00000ed0| 2f 53 55 42 3e 29 3c 53 | 55 50 3e 6e 3c 2f 53 55 |/SUB>)<S|UP>n</SU|
|00000ee0| 50 3e 20 3d 20 65 78 70 | 28 2d 20 3c 49 3e 6e 3c |P> = exp|(- <I>n<|
|00000ef0| 2f 49 3e 2f 3c 49 3e 54 | 3c 2f 49 3e 29 2c 3c 2f |/I>/<I>T|</I>),</|
|00000f00| 54 44 3e 0a 3c 54 44 20 | 57 49 44 54 48 3d 31 30 |TD>.<TD |WIDTH=10|
|00000f10| 20 41 4c 49 47 4e 3d 22 | 52 49 47 48 54 22 3e 0a | ALIGN="|RIGHT">.|
|00000f20| 28 33 29 3c 2f 54 44 3e | 3c 2f 54 52 3e 0a 3c 54 |(3)</TD>|</TR>.<T|
|00000f30| 52 20 56 41 4c 49 47 4e | 3d 22 4d 49 44 44 4c 45 |R VALIGN|="MIDDLE|
|00000f40| 22 3e 3c 54 44 20 4e 4f | 57 52 41 50 20 41 4c 49 |"><TD NO|WRAP ALI|
|00000f50| 47 4e 3d 22 52 49 47 48 | 54 22 3e 3c 49 3e 54 3c |GN="RIGH|T"><I>T<|
|00000f60| 2f 49 3e 3c 2f 54 44 3e | 0a 3c 54 44 20 57 49 44 |/I></TD>|.<TD WID|
|00000f70| 54 48 3d 22 31 30 22 20 | 41 4c 49 47 4e 3d 22 43 |TH="10" |ALIGN="C|
|00000f80| 45 4e 54 45 52 22 20 4e | 4f 57 52 41 50 3e 3d 3c |ENTER" N|OWRAP>=<|
|00000f90| 2f 54 44 3e 0a 3c 54 44 | 20 41 4c 49 47 4e 3d 22 |/TD>.<TD| ALIGN="|
|00000fa0| 4c 45 46 54 22 20 4e 4f | 57 52 41 50 3e 2d 31 2f |LEFT" NO|WRAP>-1/|
|00000fb0| 6c 6e 26 6e 62 73 70 3b | 3c 49 3e 70 3c 2f 49 3e |ln&nbsp;|<I>p</I>|
|00000fc0| 3c 53 55 42 3e 73 77 61 | 70 3c 2f 53 55 42 3e 26 |<SUB>swa|p</SUB>&|
|00000fd0| 23 38 38 30 35 3b 30 2e | 3c 2f 54 44 3e 0a 3c 54 |#8805;0.|</TD>.<T|
|00000fe0| 44 20 57 49 44 54 48 3d | 31 30 20 41 4c 49 47 4e |D WIDTH=|10 ALIGN|
|00000ff0| 3d 22 52 49 47 48 54 22 | 3e 0a 28 34 29 3c 2f 54 |="RIGHT"|>.(4)</T|
|00001000| 44 3e 3c 2f 54 52 3e 0a | 3c 2f 54 41 42 4c 45 3e |D></TR>.|</TABLE>|
|00001010| 3c 2f 44 49 56 3e 0a 3c | 42 52 20 43 4c 45 41 52 |</DIV>.<|BR CLEAR|
|00001020| 3d 22 41 4c 4c 22 3e 0a | 0a 54 68 65 20 61 6e 6e |="ALL">.|.The ann|
|00001030| 65 61 6c 69 6e 67 20 73 | 63 68 65 64 75 6c 65 20 |ealing s|chedule |
|00001040| 69 73 20 74 6f 20 6c 6f | 77 65 72 20 3c 49 3e 70 |is to lo|wer <I>p|
|00001050| 3c 2f 49 3e 3c 53 55 42 | 3e 73 77 61 70 3c 2f 53 |</I><SUB|>swap</S|
|00001060| 55 42 3e 20 74 6f 20 30 | 20 6c 69 6e 65 61 72 6c |UB> to 0| linearl|
|00001070| 79 20 77 69 74 68 20 74 | 68 65 0a 6e 75 6d 62 65 |y with t|he.numbe|
|00001080| 72 20 6f 66 20 67 61 6d | 65 73 20 61 6e 64 20 73 |r of gam|es and s|
|00001090| 65 74 20 3c 21 2d 2d 20 | 4d 41 54 48 0a 20 24 70 |et <!-- |MATH. $p|
|000010a0| 5f 7b 73 77 61 70 7d 20 | 3d 20 30 24 0a 20 2d 2d |_{swap} |= 0$. --|
|000010b0| 3e 0a 3c 49 3e 70 3c 2f | 49 3e 3c 53 55 42 3e 73 |>.<I>p</|I><SUB>s|
|000010c0| 77 61 70 3c 2f 53 55 42 | 3e 20 3d 20 30 20 28 69 |wap</SUB|> = 0 (i|
|000010d0| 2e 65 2e 20 3c 49 3e 54 | 3c 2f 49 3e 20 3d 20 30 |.e. <I>T|</I> = 0|
|000010e0| 29 20 66 6f 72 20 61 20 | 66 65 77 20 67 61 6d 65 |) for a |few game|
|000010f0| 73 0a 61 74 20 74 68 65 | 20 65 6e 64 20 74 6f 20 |s.at the| end to |
|00001100| 73 65 74 74 6c 65 20 69 | 6e 20 74 68 65 20 6e 65 |settle i|n the ne|
|00001110| 61 72 65 73 74 20 6c 6f | 63 61 6c 20 65 78 74 72 |arest lo|cal extr|
|00001120| 65 6d 75 6d 2e 20 4e 6f | 74 69 63 65 20 74 68 61 |emum. No|tice tha|
|00001130| 74 20 74 68 69 73 0a 69 | 73 20 6e 6f 74 20 74 68 |t this.i|s not th|
|00001140| 65 20 4d 65 74 72 6f 70 | 6f 6c 69 73 20 61 6c 67 |e Metrop|olis alg|
|00001150| 6f 72 69 74 68 6d 20 28 | 77 68 69 63 68 20 69 73 |orithm (|which is|
|00001160| 20 6e 6f 74 20 74 68 65 | 20 6f 6e 6c 79 20 63 68 | not the| only ch|
|00001170| 6f 69 63 65 20 70 6f 73 | 73 69 62 6c 65 0a 61 6e |oice pos|sible.an|
|00001180| 79 77 61 79 29 2e 20 57 | 65 20 66 6f 75 6e 64 20 |yway). W|e found |
|00001190| 74 68 61 74 20 66 6f 72 | 20 74 68 65 20 66 65 77 |that for| the few|
|000011a0| 20 67 61 6d 65 73 20 77 | 65 20 70 6c 61 79 20 69 | games w|e play i|
|000011b0| 74 20 64 69 64 6e 27 74 | 20 73 65 65 6d 20 74 6f |t didn't| seem to|
|000011c0| 0a 6d 61 74 74 65 72 20 | 77 68 65 74 68 65 72 20 |.matter |whether |
|000011d0| 3c 49 3e 70 3c 2f 49 3e | 3c 53 55 42 3e 73 77 61 |<I>p</I>|<SUB>swa|
|000011e0| 70 3c 2f 53 55 42 3e 20 | 64 65 70 65 6e 64 73 20 |p</SUB> |depends |
|000011f0| 6f 6e 20 74 68 65 20 76 | 61 6c 75 65 20 64 69 66 |on the v|alue dif|
|00001200| 66 65 72 65 6e 63 65 20 | 6f 72 20 6e 6f 74 2e 20 |ference |or not. |
|00001210| 20 49 6e 0a 61 64 64 69 | 74 69 6f 6e 20 61 20 66 | In.addi|tion a f|
|00001220| 65 77 20 70 65 72 63 65 | 6e 74 20 6f 66 20 61 6c |ew perce|nt of al|
|00001230| 6c 20 6d 6f 76 65 73 20 | 61 72 65 20 70 65 72 66 |l moves |are perf|
|00001240| 6f 72 6d 65 64 20 63 6f | 6d 70 6c 65 74 65 6c 79 |ormed co|mpletely|
|00001250| 20 72 61 6e 64 6f 6d 6c | 79 0a 74 6f 20 61 76 6f | randoml|y.to avo|
|00001260| 69 64 20 69 6e 66 69 6e | 69 74 65 20 28 6f 72 20 |id infin|ite (or |
|00001270| 6c 6f 6e 67 29 20 6c 6f | 6f 70 73 2e 20 46 75 72 |long) lo|ops. Fur|
|00001280| 74 68 65 72 20 65 78 70 | 65 72 69 6d 65 6e 74 61 |ther exp|erimenta|
|00001290| 74 69 6f 6e 20 69 6e 20 | 63 6f 6e 6a 75 6e 63 74 |tion in |conjunct|
|000012a0| 69 6f 6e 0a 77 69 74 68 | 20 61 20 6d 65 61 73 75 |ion.with| a measu|
|000012b0| 72 65 20 6f 66 20 68 6f | 77 20 77 65 6c 6c 20 74 |re of ho|w well t|
|000012c0| 68 65 20 61 6e 6e 65 61 | 6c 69 6e 67 20 70 72 6f |he annea|ling pro|
|000012d0| 63 65 73 73 20 77 6f 72 | 6b 73 20 69 73 20 6e 65 |cess wor|ks is ne|
|000012e0| 65 64 65 64 2e 0a 0a 3c | 50 3e 0a 47 6f 62 62 6c |eded...<|P>.Gobbl|
|000012f0| 65 20 77 61 73 20 64 65 | 76 65 6c 6f 70 65 64 20 |e was de|veloped |
|00001300| 6f 6e 20 61 20 32 38 36 | 2f 31 36 20 50 43 2c 20 |on a 286|/16 PC, |
|00001310| 77 68 69 63 68 20 74 72 | 61 6e 73 6c 61 74 65 73 |which tr|anslates|
|00001320| 20 69 6e 74 6f 20 76 65 | 72 79 20 73 6c 6f 77 0a | into ve|ry slow.|
|00001330| 61 6e 64 20 70 6f 77 65 | 72 6c 65 73 73 20 62 79 |and powe|rless by|
|00001340| 20 74 6f 64 61 79 73 20 | 77 6f 72 6b 73 74 61 74 | todays |workstat|
|00001350| 69 6f 6e 20 73 74 61 6e | 64 61 72 64 73 2e 20 57 |ion stan|dards. W|
|00001360| 65 20 72 65 73 74 72 69 | 63 74 20 6f 75 72 0a 61 |e restri|ct our.a|
|00001370| 74 74 65 6e 74 69 6f 6e | 20 74 6f 20 74 68 65 20 |ttention| to the |
|00001380| 39 78 39 20 62 6f 61 72 | 64 2e 20 4f 6e 65 20 69 |9x9 boar|d. One i|
|00001390| 6d 70 6f 72 74 61 6e 74 | 20 61 73 70 65 63 74 20 |mportant| aspect |
|000013a0| 6f 66 20 73 74 61 74 69 | 73 74 69 63 61 6c 0a 6d |of stati|stical.m|
|000013b0| 65 74 68 6f 64 73 20 6c | 69 6b 65 20 73 69 6d 75 |ethods l|ike simu|
|000013c0| 6c 61 74 65 64 20 61 6e | 6e 65 61 6c 69 6e 67 20 |lated an|nealing |
|000013d0| 69 73 20 74 68 61 74 20 | 73 6f 6d 65 20 6d 69 6e |is that |some min|
|000013e0| 69 6d 61 6c 20 61 6d 6f | 75 6e 74 20 6f 66 20 64 |imal amo|unt of d|
|000013f0| 61 74 61 0a 69 73 20 6e | 65 65 64 65 64 20 74 6f |ata.is n|eeded to|
|00001400| 20 66 69 6e 64 20 74 68 | 65 20 73 69 67 6e 61 6c | find th|e signal|
|00001410| 20 69 6e 20 74 68 65 20 | 6e 6f 69 73 65 2e 20 4c | in the |noise. L|
|00001420| 65 74 20 75 73 20 64 65 | 6e 6f 74 65 20 62 79 20 |et us de|note by |
|00001430| 73 74 72 61 74 65 67 79 | 20 41 0a 74 68 65 20 61 |strategy| A.the a|
|00001440| 6c 67 6f 72 69 74 68 6d | 20 6f 66 20 6f 72 64 65 |lgorithm| of orde|
|00001450| 72 20 30 20 64 65 73 63 | 72 69 62 65 64 20 69 6e |r 0 desc|ribed in|
|00001460| 20 74 68 65 20 70 72 65 | 76 69 6f 75 73 20 73 65 | the pre|vious se|
|00001470| 63 74 69 6f 6e 2e 20 53 | 74 72 61 74 65 67 79 20 |ction. S|trategy |
|00001480| 41 0a 72 65 71 75 69 72 | 65 73 20 73 65 76 65 72 |A.requir|es sever|
|00001490| 61 6c 20 68 75 6e 64 72 | 65 64 20 67 61 6d 65 73 |al hundr|ed games|
|000014a0| 20 74 6f 20 62 65 20 70 | 6c 61 79 65 64 20 62 65 | to be p|layed be|
|000014b0| 66 6f 72 65 20 74 68 65 | 20 64 61 74 61 20 69 73 |fore the| data is|
|000014c0| 0a 72 65 61 73 6f 6e 61 | 62 6c 79 20 72 65 6c 69 |.reasona|bly reli|
|000014d0| 61 62 6c 65 20 77 68 69 | 63 68 20 74 61 6b 65 73 |able whi|ch takes|
|000014e0| 20 6f 6e 20 74 68 65 20 | 6f 72 64 65 72 20 6f 66 | on the |order of|
|000014f0| 20 31 20 6d 69 6e 75 74 | 65 20 6f 6e 20 74 68 65 | 1 minut|e on the|
|00001500| 20 50 43 20 61 6e 64 0a | 61 20 66 65 77 20 73 65 | PC and.|a few se|
|00001510| 63 6f 6e 64 73 20 6f 6e | 20 61 20 49 42 4d 2f 52 |conds on| a IBM/R|
|00001520| 49 53 43 20 77 6f 72 6b | 73 74 61 74 69 6f 6e 2e |ISC work|station.|
|00001530| 20 28 54 79 70 69 63 61 | 6c 20 70 68 79 73 69 63 | (Typica|l physic|
|00001540| 73 20 61 70 70 6c 69 63 | 61 74 69 6f 6e 73 0a 69 |s applic|ations.i|
|00001550| 6e 20 4d 6f 6e 74 65 20 | 43 61 72 6c 6f 20 61 72 |n Monte |Carlo ar|
|00001560| 65 20 61 6c 6c 6f 77 65 | 64 20 74 6f 20 72 75 6e |e allowe|d to run|
|00001570| 20 66 6f 72 20 64 61 79 | 73 20 6f 72 20 77 65 65 | for day|s or wee|
|00001580| 6b 73 2c 20 62 75 74 20 | 77 65 20 68 61 76 65 20 |ks, but |we have |
|00001590| 67 61 6d 65 0a 70 6c 61 | 79 20 77 69 74 68 20 68 |game.pla|y with h|
|000015a0| 75 6d 61 6e 73 20 69 6e | 20 6d 69 6e 64 2e 29 0a |umans in| mind.).|
|000015b0| 0a 3c 50 3e 0a 0a 3c 48 | 52 3e 0a 0a 3c 2f 42 4f |.<P>..<H|R>..</BO|
|000015c0| 44 59 3e 0a 3c 2f 48 54 | 4d 4c 3e 0a             |DY>.</HT|ML>.    |
+--------+-------------------------+-------------------------+--------+--------+